package main.leetcode.primary.from001to100;

import java.util.Arrays;

/**
 * 31.下一个排列
 *
 * <p>实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
 *
 * <p>如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
 *
 * <p>必须原地修改，只允许使用额外常数空间。
 *
 * <p>以下是一些例子，输入位于左侧列，其相应输出位于右侧列。 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/next-permutation
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex31 {
    // 找第一个升序的尾巴
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        // 找到第一个升降序临界点
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            --i;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            // 找到i右侧第一个比nums[i]大的数
            while (j >= 0 && nums[j] <= nums[i]) {
                --j;
            }
            nums[i] = nums[i] + nums[j] - (nums[j] = nums[i]);
        }
        Arrays.sort(nums, i + 1, nums.length);
    }
}
